!function (e) {
    if ("object" == typeof exports && "undefined" != typeof module)module.exports = e(); else if ("function" == typeof define && define.amd)define([], e); else {
        var n;
        n = "undefined" != typeof window ? window : "undefined" != typeof global ? global : "undefined" != typeof self ? self : this, n.earcut = e()
    }
}(function () {
    return function e(n, r, t) {
        function i(f, o) {
            if (!r[f]) {
                if (!n[f]) {
                    var x = "function" == typeof require && require;
                    if (!o && x)return x(f, !0);
                    if (u)return u(f, !0);
                    var v = new Error("Cannot find module '" + f + "'");
                    throw v.code = "MODULE_NOT_FOUND", v
                }
                var p = r[f] = {exports: {}};
                n[f][0].call(p.exports, function (e) {
                    var r = n[f][1][e];
                    return i(r ? r : e)
                }, p, p.exports, e, n, r, t)
            }
            return r[f].exports
        }

        for (var u = "function" == typeof require && require, f = 0; f < t.length; f++)i(t[f]);
        return i
    }({
        1: [function (e, n, r) {
            "use strict";
            function t(e, n, r) {
                r = r || 2;
                var t = n && n.length, o = t ? n[0] * r : e.length, x = u(e, i(e, 0, o, r, !0)), v = [];
                if (!x)return v;
                var l, a, Z, c, s, h, d;
                if (t && (x = p(e, n, x, r)), e.length > 80 * r) {
                    l = Z = e[0], a = c = e[1];
                    for (var w = r; o > w; w += r)s = e[w], h = e[w + 1], l > s && (l = s), a > h && (a = h), s > Z && (Z = s), h > c && (c = h);
                    d = Math.max(Z - l, c - a)
                }
                return f(e, x, v, r, l, a, d), v
            }

            function i(e, n, r, t, i) {
                var u, f, o, x = 0;
                for (u = n, f = r - t; r > u; u += t)x += (e[f] - e[u]) * (e[u + 1] + e[f + 1]), f = u;
                if (i === x > 0)for (u = n; r > u; u += t)o = M(u, o); else for (u = r - t; u >= n; u -= t)o = M(u, o);
                return o
            }

            function u(e, n, r) {
                r || (r = n);
                var t, i = n;
                do if (t = !1, i.steiner || !g(e, i.i, i.next.i) && 0 !== w(e, i.prev.i, i.i, i.next.i))i = i.next; else {
                    if (i.prev.next = i.next, i.next.prev = i.prev, i.prevZ && (i.prevZ.nextZ = i.nextZ), i.nextZ && (i.nextZ.prevZ = i.prevZ), i = r = i.prev, i === i.next)return null;
                    t = !0
                } while (t || i !== r);
                return r
            }

            function f(e, n, r, t, i, p, l, a) {
                if (n) {
                    a || void 0 === i || Z(e, n, i, p, l);
                    for (var c, s, h = n; n.prev !== n.next;)if (c = n.prev, s = n.next, o(e, n, i, p, l))r.push(c.i / t), r.push(n.i / t), r.push(s.i / t), s.prev = c, c.next = s, n.prevZ && (n.prevZ.nextZ = n.nextZ), n.nextZ && (n.nextZ.prevZ = n.prevZ), n = s.next, h = s.next; else if (n = s, n === h) {
                        a ? 1 === a ? (n = x(e, n, r, t), f(e, n, r, t, i, p, l, 2)) : 2 === a && v(e, n, r, t, i, p, l) : f(e, u(e, n), r, t, i, p, l, 1);
                        break
                    }
                }
            }

            function o(e, n, r, t, i) {
                var u = n.prev.i, f = n.i, o = n.next.i, x = e[u], v = e[u + 1], p = e[f], l = e[f + 1], a = e[o], Z = e[o + 1], c = x * l - v * p, h = x * Z - v * a, d = a * l - Z * p, w = c - h - d;
                if (0 >= w)return !1;
                var g, y, z, b, m, q, M, O = Z - v, D = x - a, E = v - l, N = p - x;
                if (void 0 !== r) {
                    var U = p > x ? a > x ? x : a : a > p ? p : a, _ = l > v ? Z > v ? v : Z : Z > l ? l : Z, j = x > p ? x > a ? x : a : p > a ? p : a, k = v > l ? v > Z ? v : Z : l > Z ? l : Z, C = s(U, _, r, t, i), F = s(j, k, r, t, i);
                    for (M = n.nextZ; M && M.z <= F;)if (g = M.i, M = M.nextZ, g !== u && g !== o && (y = e[g], z = e[g + 1], b = O * y + D * z - h, b >= 0 && (m = E * y + N * z + c, m >= 0 && (q = w - b - m, q >= 0 && (b && m || b && q || m && q)))))return !1;
                    for (M = n.prevZ; M && M.z >= C;)if (g = M.i, M = M.prevZ, g !== u && g !== o && (y = e[g], z = e[g + 1], b = O * y + D * z - h, b >= 0 && (m = E * y + N * z + c, m >= 0 && (q = w - b - m, q >= 0 && (b && m || b && q || m && q)))))return !1
                } else for (M = n.next.next; M !== n.prev;)if (g = M.i, M = M.next, y = e[g], z = e[g + 1], b = O * y + D * z - h, b >= 0 && (m = E * y + N * z + c, m >= 0 && (q = w - b - m, q >= 0 && (b && m || b && q || m && q))))return !1;
                return !0
            }

            function x(e, n, r, t) {
                var i = n;
                do {
                    var u = i.prev, f = i.next.next;
                    if (u.i !== f.i && y(e, u.i, i.i, i.next.i, f.i) && b(e, u, f) && b(e, f, u)) {
                        r.push(u.i / t), r.push(i.i / t), r.push(f.i / t), u.next = f, f.prev = u;
                        var o = i.prevZ, x = i.nextZ && i.nextZ.nextZ;
                        o && (o.nextZ = x), x && (x.prevZ = o), i = n = f
                    }
                    i = i.next
                } while (i !== n);
                return i
            }

            function v(e, n, r, t, i, o, x) {
                var v = n;
                do {
                    for (var p = v.next.next; p !== v.prev;) {
                        if (v.i !== p.i && d(e, v, p)) {
                            var l = q(v, p);
                            return v = u(e, v, v.next), l = u(e, l, l.next), f(e, v, r, t, i, o, x), void f(e, l, r, t, i, o, x)
                        }
                        p = p.next
                    }
                    v = v.next
                } while (v !== n)
            }

            function p(e, n, r, t) {
                var f, o, x, v, p, a = [];
                for (f = 0, o = n.length; o > f; f++)x = n[f] * t, v = o - 1 > f ? n[f + 1] * t : e.length, p = i(e, x, v, t, !1), p === p.next && (p.steiner = !0), p = u(e, p), p && a.push(h(e, p));
                for (a.sort(function (n, r) {
                    return e[n.i] - e[r.i]
                }), f = 0; f < a.length; f++)l(e, a[f], r), r = u(e, r, r.next);
                return r
            }

            function l(e, n, r) {
                if (r = a(e, n, r)) {
                    var t = q(r, n);
                    u(e, t, t.next)
                }
            }

            function a(e, n, r) {
                var t, i, u, f = r, o = n.i, x = e[o], v = e[o + 1], p = -(1 / 0);
                do {
                    if (i = f.i, u = f.next.i, v <= e[i + 1] && v >= e[u + 1]) {
                        var l = e[i] + (v - e[i + 1]) * (e[u] - e[i]) / (e[u + 1] - e[i + 1]);
                        x >= l && l > p && (p = l, t = e[i] < e[u] ? f : f.next)
                    }
                    f = f.next
                } while (f !== r);
                if (!t)return null;
                var a, Z, c, s, h, d, w = e[t.i], g = e[t.i + 1], y = x * g - v * w, z = x * v - v * p, m = v - v, q = x - p, M = v - g, O = w - x, D = y - z - (p * g - v * w), E = 0 >= D ? -1 : 1, N = t, U = 1 / 0;
                for (f = t.next; f !== N;)a = e[f.i], Z = e[f.i + 1], c = x - a, c >= 0 && a >= w && (s = (m * a + q * Z - z) * E, s >= 0 && (h = (M * a + O * Z + y) * E, h >= 0 && D * E - s - h >= 0 && (d = Math.abs(v - Z) / c, U > d && b(e, f, n) && (t = f, U = d)))), f = f.next;
                return t
            }

            function Z(e, n, r, t, i) {
                var u = n;
                do null === u.z && (u.z = s(e[u.i], e[u.i + 1], r, t, i)), u.prevZ = u.prev, u.nextZ = u.next, u = u.next; while (u !== n);
                u.prevZ.nextZ = null, u.prevZ = null, c(u)
            }

            function c(e) {
                var n, r, t, i, u, f, o, x, v = 1;
                do {
                    for (r = e, e = null, u = null, f = 0; r;) {
                        for (f++, t = r, o = 0, n = 0; v > n && (o++, t = t.nextZ, t); n++);
                        for (x = v; o > 0 || x > 0 && t;)0 === o ? (i = t, t = t.nextZ, x--) : 0 !== x && t ? r.z <= t.z ? (i = r, r = r.nextZ, o--) : (i = t, t = t.nextZ, x--) : (i = r, r = r.nextZ, o--), u ? u.nextZ = i : e = i, i.prevZ = u, u = i;
                        r = t
                    }
                    u.nextZ = null, v *= 2
                } while (f > 1);
                return e
            }

            function s(e, n, r, t, i) {
                return e = 1e3 * (e - r) / i, e = 16711935 & (e | e << 8), e = 252645135 & (e | e << 4), e = 858993459 & (e | e << 2), e = 1431655765 & (e | e << 1), n = 1e3 * (n - t) / i, n = 16711935 & (n | n << 8), n = 252645135 & (n | n << 4), n = 858993459 & (n | n << 2), n = 1431655765 & (n | n << 1), e | n << 1
            }

            function h(e, n) {
                var r = n, t = n;
                do e[r.i] < e[t.i] && (t = r), r = r.next; while (r !== n);
                return t
            }

            function d(e, n, r) {
                return !z(e, n, n.i, r.i) && b(e, n, r) && b(e, r, n) && m(e, n, n.i, r.i)
            }

            function w(e, n, r, t) {
                var i = (e[r + 1] - e[n + 1]) * (e[t] - e[r]) - (e[r] - e[n]) * (e[t + 1] - e[r + 1]);
                return i > 0 ? 1 : 0 > i ? -1 : 0
            }

            function g(e, n, r) {
                return e[n] === e[r] && e[n + 1] === e[r + 1]
            }

            function y(e, n, r, t, i) {
                return w(e, n, r, t) !== w(e, n, r, i) && w(e, t, i, n) !== w(e, t, i, r)
            }

            function z(e, n, r, t) {
                var i = n;
                do {
                    var u = i.i, f = i.next.i;
                    if (u !== r && f !== r && u !== t && f !== t && y(e, u, f, r, t))return !0;
                    i = i.next
                } while (i !== n);
                return !1
            }

            function b(e, n, r) {
                return -1 === w(e, n.prev.i, n.i, n.next.i) ? -1 !== w(e, n.i, r.i, n.next.i) && -1 !== w(e, n.i, n.prev.i, r.i) : -1 === w(e, n.i, r.i, n.prev.i) || -1 === w(e, n.i, n.next.i, r.i)
            }

            function m(e, n, r, t) {
                var i = n, u = !1, f = (e[r] + e[t]) / 2, o = (e[r + 1] + e[t + 1]) / 2;
                do {
                    var x = i.i, v = i.next.i;
                    e[x + 1] > o != e[v + 1] > o && f < (e[v] - e[x]) * (o - e[x + 1]) / (e[v + 1] - e[x + 1]) + e[x] && (u = !u), i = i.next
                } while (i !== n);
                return u
            }

            function q(e, n) {
                var r = new O(e.i), t = new O(n.i), i = e.next, u = n.prev;
                return e.next = n, n.prev = e, r.next = i, i.prev = r, t.next = r, r.prev = t, u.next = t, t.prev = u, t
            }

            function M(e, n) {
                var r = new O(e);
                return n ? (r.next = n.next, r.prev = n, n.next.prev = r, n.next = r) : (r.prev = r, r.next = r), r
            }

            function O(e) {
                this.i = e, this.prev = null, this.next = null, this.z = null, this.prevZ = null, this.nextZ = null, this.steiner = !1
            }

            n.exports = t
        }, {}]
    }, {}, [1])(1)
});
